Conventional computerized devices include a processor (e.g., microprocessor, controller or central processing unit) that is capable of executing, interpreting, operating or otherwise performing computer program instructions (e.g., software code) associated with computer programs stored in a memory system within the computerized device. During execution of a computer program, instructions in the computer program may direct the processor to allocate various portions of memory in order to store data structures for use by the computer program. As an example, in the C programming language, a programmer can provide a malloc instruction for use with a data structure variable name as a parameter in order to cause the computerized device to reserve an area of memory equivalent in size to the data structure for use by the program containing the malloc instruction. Once the computer program is finished using the data structure, the programmer that created the computer program can include a free instruction that causes the processor to release the memory formerly allocated to the data structure for use by subsequent allocation requests within the computerized device.
Some conventional execution environments that operate within computerized devices automatically control the allocation and deallocation or release of memory on behalf of computer program processes. In such cases, the programmer does not need to provide specific instructions to allocate and deallocate memory. As an example, in the Java programming language (Java is a registered trademark of Sun Microsystems, Inc.), a programmer can create a program such as a Java applet and can create or define objects (i.e., data structures) in the Java applet as needed, without being concerned about the allocation or deallocation (i.e., release) of memory required to store and/or maintain the objects and associated data during operation of the Java applet. Instead, during runtime, the Java applet operates on a computerized device within an execution environment called a Java virtual machine or JVM. A conventional Java virtual machine interprets the Java computer program code within the Java applet and handles all processing operations associated with allocating or reserving memory on behalf of the Java applet for objects instantiated by that Java applet. In addition, a conventional Java virtual machine performs a periodic memory management technique called “garbage collection” in order to traverse memory and deallocate portions of memory which store object data that is no longer referenced by any objects in any Java processes or threads (e.g., by any applets). In this manner, the automatic memory allocation and deallocation mechanisms or garbage collection techniques operate as part of the Java virtual machine in order to handle allocation and deallocation of memory on behalf of Java processes or threads.
Continuing with the aforementioned example of a Java thread or process operating within a Java virtual machine, a conventional Java virtual machine provides a storage structure such as a stack to the Java thread. During operation of the Java thread, the Java virtual machine, on behalf of the Java thread or process, can place information onto (i.e., push) and off-of (i.e., pop) the stack on behalf of the Java thread associated with that stack. As a specific example, if a Java thread instantiates a series of objects A, B and C, the Java virtual machine allocates memory for each of these objects in a general memory area referred to as a heap. During operation of the Java thread, the Java virtual machine can reference the objects in a heap via pointers to those objects. The Java thread may perhaps call or otherwise transfer processing to another routine. In such cases, a conventional Java virtual machine may place references to the objects A, B and C associated with the Java thread onto a call-stack associated with the Java thread prior to the transfer of processing into the routine. The stack or call-stack thus contains such things as local variables, some of which may be references into the heap, and any intermediate but still live results saved from registers at a particular program counter location.
In other cases, an operating system might instruct the Java virtual machine to begin operation or execution (e.g., interpretation) of another Java thread. The first Java thread from which control was transferred may enter an idle or passive state or condition for an indefinite period of time. Perhaps the first Java thread becomes blocked while awaiting an event to occur. Information may be pushed onto the stack when a thread enters an idle condition. Within the Java execution environment, there may be many threads existing at any point in time. The stack associated with each of these Java threads may contain references to the general memory area or heap for objects associated with those threads.
As noted above, in a typical conventional Java virtual machine, each Java thread has a stack. The stack is composed of a set of frames, sometimes called activation records. Each frame consists of a set of cells or words. For the purposes of stack scanning, a word contains either a reference (root) to an object in the heap or a non-reference value. Example of non-reference values include integers, floating point values, return addresses, and the like. Frames are private to a thread and thus only a thread or the garbage collector may modify the cells contents of a frame. A frame is usually associated with a Java method (e.g., a routine or subroutine). When a thread is executing in a Java method, the corresponding frame is active. The active frame is always the topmost frame on the stack. A thread is not able to modify the contents of non-active frames.
As an example, suppose mA, mB, mC and mD are Java methods. Futher suppose mA calls into a mB, and mB calls into mC, and mC then calls into mD. Conceptually, the stack will then look like: {fA, fB, fC, fD)}, where fA is the frame associated with Java method mA, fB is the frame associated with Java method mB, and so forth. The frame fD (at the top of the stack) is the active frame while fA is the oldest frame. While fD is active the thread can't access the contents of frames fA, fB, fC. More specifically, the thread can't “name” the locations so it can't refer to them. When mD returns control into mC, we say the stack unwinds. At this point, the stack will have the following form: {fA, fB, fC} and the frame fC is the active frame.
As noted above, the Java virtual machine is responsible for deallocating memory on behalf of Java threads. To do so, the Java virtual machine typically performs a conventional garbage collection memory management technique for threads associated with the Java virtual machine. Such a conventional garbage collection memory management technique involves identifying or differentiating those portions of the heap or other general memory area that are no longer referenced by any Java threads as opposed to those portions of memory that are allocated to storing objects on behalf of thread. By identifying the used versus the unused areas of memory, some garbage collection technique can maintain a free list of the unused memory portions or areas for later use when an active or executing Java thread requires the instantiation of a new object in memory.
One technique used by conventional garbage collection memory management techniques to identify those areas of a heap that contain allocated memory (i.e., that contain object data in use by threads) operates by scanning the stacks associated with all threads in order to identify all references to objects in the heap. Those areas or portions of the heap that are not referenced within any of the stacks associated with the threads within that Java virtual machine are considered to be garbage. In other words, upon each operation of garbage collection, by scanning the stacks associated with the threads in a Java virtual machine, the garbage collection technique can identify all areas of the heap that are in use and thus those areas not identified are considered to be free memory and may be freely allocated upon the next request for heap memory.
Conventional stack scanning operations are transitive in that if a root reference (i.e., a reference to heap memory stored outside of the heap, such as in the stack) references a heap object (e.g., object A) which contains an intra-heap reference to another object (e.g., object B), the scan operation will note or otherwise detect that both objects A and B are reachable from the root. The scanning operation thus “traces” intra-object references to determine reachable heap memory portions.
During the process of garbage collection, some conventional garbage collection techniques, called “moving” or “copying” garbage collectors, go so far as to rearrange the general memory area (i.e., the heap) in order to coalesce or condense all areas of free memory (i.e., those areas not allocated to objects associated with threads) into a single contiguous area of free memory within the general memory area. This significantly overcomes a problem of memory fragmentation that occurs when there are many smaller non-contiguous portions of free memory. The garbage collection processing can thus move allocated portions of memory around (i.e., can mode data associated with objects) in order to group this allocated data into a single contiguous portion of allocated memory. The result is to thus collect many small unused but noncontiguous portions of free memory in order to make large portions of continuous free memory available should a need arise to allocate such memory. However, if a conventional garbage collection technique moves data within the heap that is allocated to an object associated with a thread (i.e., moves an existing object that is not garbage) in order to coalesce free memory, the conventional garbage collection technique must keep track of memory addresses before and after the move of the object data within the heap. Once the heap has been rearranged in order to group free memory into one or more large contiguous portions, the conventional garbage collection technique must return to the stacks of each thread in order to update the references (i.e., pointers or memory addresses) within those stacks to correctly point to or reference each object that was moved within the heap during the garbage collection process. In other words, if a conventional garbage collection process moves objects around within the heap, the garbage collection process must update the new locations of those objects within the stacks associated with the threads so that those threads can properly reference those objects. Conventional copying or moving garbage collectors can also adjust intra-heap (e.g., intra-object) references when object are moved during the garbage collection process.